package main.od;

import java.util.Scanner;

public class MonkeyJump {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (!(n > 0 && n <= 50)){
            System.out.println("input invalid!");
        }
        System.out.println("the result is: " + calculate(n));
        System.out.println("the result2 is: " + calculate2(n));
    }
    public static int calculate(int n){
        if (n < 3){
            return 1;
        }
        return calculate(n - 1) + calculate(n - 3);
    }

    public static int calculate2(int n){
        int[] dp = new int[n + 1];
        if (n < 3){
            return 1;
        }
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3;i <= n;i++){
            dp[i] = dp[i - 1] + dp[i - 3];
        }
        return dp[n];
    }
}
